home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / Ken Long / rinth / maze.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-12-04  |  15.1 KB  |  571 lines  |  [TEXT/UNIX]
  1. #ifndef lint
  2. static char sccsid[] = "@(#)maze.c 1.10 89/09/06 SMI";
  3. #endif
  4.  
  5. #include <sunwindow/window_hs.h>
  6. #include <sunwindow/cms.h>
  7. #include <suntool/gfxsw.h>
  8. #include <stdio.h>
  9.  
  10. #define COLOR_MAP_SIZE    4
  11. #define LOGOSIZE    7
  12. #define MIN_MAZE_SIZE    3
  13.  
  14. /* The following limits are adequate for displays up to 2048x2048 */
  15. #define MAX_MAZE_SIZE_X    205
  16. #define MAX_MAZE_SIZE_Y    205
  17.  
  18. #define LOCK_COUNT_1    50
  19. #define LOCK_COUNT_2    100
  20.  
  21. #define MOVE_LIST_SIZE  (MAX_MAZE_SIZE_X * MAX_MAZE_SIZE_Y)
  22.  
  23. #define WALL_TOP    0x8000
  24. #define WALL_RIGHT    0x4000
  25. #define WALL_BOTTOM    0x2000
  26. #define WALL_LEFT    0x1000
  27.  
  28. #define DOOR_IN_TOP    0x800
  29. #define DOOR_IN_RIGHT    0x400
  30. #define DOOR_IN_BOTTOM    0x200
  31. #define DOOR_IN_LEFT    0x100
  32. #define DOOR_IN_ANY    0xF00
  33.  
  34. #define DOOR_OUT_TOP    0x80
  35. #define DOOR_OUT_RIGHT    0x40
  36. #define DOOR_OUT_BOTTOM    0x20
  37. #define DOOR_OUT_LEFT    0x10
  38.  
  39. #define START_SQUARE    0x2
  40. #define END_SQUARE    0x1
  41.  
  42. #define SQ_SIZE_X    10
  43. #define SQ_SIZE_Y    10
  44.  
  45. #define NUM_RANDOM    100
  46.  
  47. static u_char rmap[COLOR_MAP_SIZE], gmap[COLOR_MAP_SIZE], bmap[COLOR_MAP_SIZE];
  48. static long int randnum[NUM_RANDOM];
  49. static struct gfxsubwindow *gfx;
  50. static struct rect pwrect;
  51.  
  52. static u_short maze[MAX_MAZE_SIZE_X][MAX_MAZE_SIZE_Y];
  53.  
  54. static struct {
  55.     u_char x;
  56.     u_char y;
  57.     u_char dir;
  58.     } move_list[MOVE_LIST_SIZE], save_path[MOVE_LIST_SIZE], path[MOVE_LIST_SIZE];
  59.  
  60. static int maze_size_x, maze_size_y, border_x, border_y;
  61. static int sqnum, cur_sq_x, cur_sq_y, path_length;
  62. static int start_x, start_y, start_dir, end_x, end_y, end_dir;
  63. static int maze_restart_flag, lockcount, colorwindows, random_index;
  64. static int logo_x, logo_y, global_restart;
  65.  
  66. static  u_short icon_data[256] = {
  67. #include <images/lockscreen.icon>
  68. };
  69.  
  70. mpr_static(icon_mpr, 64, 64, 1, icon_data);
  71.  
  72.  
  73. /* main module */
  74. main(argc,argv)
  75.     int argc;
  76.     char **argv;
  77. {
  78.  
  79.     make_color_map();
  80.     initialize_window();
  81.     clear_window();
  82.     srandom(getpid());
  83.     while (1) {
  84.         set_maze_sizes(argc, argv);
  85.         if (global_restart) {
  86.             global_restart = 0;
  87.             continue;
  88.         }
  89.  
  90.  
  91.         initialize_maze();
  92.         if (global_restart) {
  93.             global_restart = 0;
  94.             continue;
  95.         }
  96.  
  97.         clear_window();
  98.         if (global_restart) {
  99.             global_restart = 0;
  100.             continue;
  101.         }
  102.  
  103.         draw_maze_border();
  104.         if (global_restart) {
  105.             global_restart = 0;
  106.             continue;
  107.         }
  108.  
  109.         create_maze();
  110.         if (global_restart) {
  111.             global_restart = 0;
  112.             continue;
  113.         }
  114.  
  115.         sleep(1);
  116.  
  117.         solve_maze();
  118.         if (global_restart) {
  119.             global_restart = 0;
  120.             continue;
  121.         }
  122.  
  123.         sleep(1);
  124.     }
  125. } /*  end of main() */
  126.  
  127.  
  128. get_random(modulo)
  129.     int modulo;
  130. {
  131.     return ((random()>>10) % modulo);
  132.  
  133. } /* end of get_random */
  134.  
  135.  
  136. make_color_map() /* make the colormap */
  137. {
  138.     register int i;
  139.  
  140.     rmap[0] = 0;
  141.     gmap[0] = 0;
  142.     bmap[0] = 0;
  143.  
  144.     rmap[1] = 255;
  145.     gmap[1] = 255;
  146.     bmap[1] = 255;
  147.  
  148.     rmap[2] = 255;
  149.     gmap[2] = 0;
  150.     bmap[2] = 0;
  151.  
  152.     rmap[3] = 90;
  153.     gmap[3] = 150;
  154.     bmap[3] = 255;
  155.  
  156. } /* end of make_colormap() */
  157.  
  158.  
  159. initialize_window() /* take over and initialize window */
  160. {
  161.     char cmsname[CMS_NAMESIZE];
  162.         gfx = gfxsw_init(0,0);
  163.     sprintf(cmsname, "maze%d", COLOR_MAP_SIZE);
  164.         pw_setcmsname(gfx->gfx_pixwin, cmsname);
  165.     colorwindows = gfx->gfx_pixwin->pw_pixrect->pr_depth > 1;
  166.     pw_putcolormap(gfx->gfx_pixwin, 0,
  167.         colorwindows ? COLOR_MAP_SIZE : 2, rmap, gmap, bmap);
  168.     pw_exposed(gfx->gfx_pixwin);
  169.         win_getrect(gfx->gfx_pixwin->pw_clipdata->pwcd_windowfd, &pwrect);
  170. } /* end of initialize_window() */
  171.  
  172.  
  173. clear_window() /* blank the window */
  174. {
  175.         pw_rop(gfx->gfx_pixwin, 0, 0,
  176.                 gfx->gfx_pixwin->pw_clipdata->pwcd_prmulti->pr_size.x,
  177.                 gfx->gfx_pixwin->pw_clipdata->pwcd_prmulti->pr_size.y,
  178.                 PIX_CLR, 0, 0, 0);
  179.  
  180. } /* end of clear_window() */
  181.  
  182.  
  183. set_maze_sizes(argc, argv)
  184.     int argc;
  185.     char **argv;
  186. {
  187.     border_x = 20;
  188.     border_y = 20;
  189.  
  190.     maze_size_x = ( gfx->gfx_pixwin->pw_clipdata->pwcd_prmulti->pr_size.x - 
  191.         border_x) / SQ_SIZE_X;
  192.     maze_size_y = ( gfx->gfx_pixwin->pw_clipdata->pwcd_prmulti->pr_size.y - 
  193.         border_y ) / SQ_SIZE_Y;
  194.  
  195.     if ( maze_size_x < 3 || SQ_SIZE_Y < 3) {
  196.         fprintf(stderr, "maze too small, exitting\n");
  197.         exit (1);
  198.     }
  199.  
  200.     border_x = ( gfx->gfx_pixwin->pw_clipdata->pwcd_prmulti->pr_size.x -
  201.                 maze_size_x * SQ_SIZE_X)/2;
  202.     border_y = ( gfx->gfx_pixwin->pw_clipdata->pwcd_prmulti->pr_size.y -
  203.                 maze_size_y * SQ_SIZE_Y)/2;
  204.  
  205. } /* end of set_maze_sizes */
  206.  
  207.  
  208. initialize_maze() /* draw the surrounding wall and start/end squares */
  209. {
  210.     register int i, j, wall;
  211.  
  212.     /* initialize all squares */
  213.     for ( i=0; i<maze_size_x; i++) {
  214.         for ( j=0; j<maze_size_y; j++) {
  215.             maze[i][j] = 0;
  216.         }
  217.     }
  218.  
  219.     /* top wall */
  220.     for ( i=0; i<maze_size_x; i++ ) {
  221.         maze[i][0] |= WALL_TOP;
  222.     }
  223.  
  224.     /* right wall */
  225.     for ( j=0; j<maze_size_y; j++ ) {
  226.         maze[maze_size_x-1][j] |= WALL_RIGHT;
  227.     }
  228.  
  229.     /* bottom wall */
  230.     for ( i=0; i<maze_size_x; i++ ) {
  231.         maze[i][maze_size_y-1] |= WALL_BOTTOM;
  232.     }
  233.  
  234.     /* left wall */
  235.     for ( j=0; j<maze_size_y; j++ ) {
  236.         maze[0][j] |= WALL_LEFT;
  237.     }
  238.  
  239.     /* set start square */
  240.     wall = get_random(4);
  241.     switch (wall) {
  242.         case 0:    
  243.             i = get_random(maze_size_x);
  244.             j = 0;
  245.             break;
  246.         case 1:    
  247.             i = maze_size_x - 1;
  248.             j = get_random(maze_size_y);
  249.             break;
  250.         case 2:    
  251.             i = get_random(maze_size_x);
  252.             j = maze_size_y - 1;
  253.             break;
  254.         case 3:    
  255.             i = 0;
  256.             j = get_random(maze_size_y);
  257.             break;
  258.     }
  259.     maze[i][j] |= START_SQUARE;
  260.     maze[i][j] |= ( DOOR_IN_TOP >> wall );
  261.     maze[i][j] &= ~( WALL_TOP >> wall );
  262.     cur_sq_x = i;
  263.     cur_sq_y = j;
  264.     start_x = i;
  265.     start_y = j;
  266.     start_dir = wall;
  267.     sqnum = 0;
  268.  
  269.         /* set end square */
  270.         wall = (wall + 2)%4;
  271.         switch (wall) {
  272.                 case 0:
  273.             i = get_random(maze_size_x);
  274.                         j = 0;
  275.                         break;
  276.                 case 1:
  277.                         i = maze_size_x - 1;
  278.             j = get_random(maze_size_y);
  279.                         break;
  280.                 case 2:
  281.             i = get_random(maze_size_x);
  282.                         j = maze_size_y - 1;
  283.                         break;
  284.                 case 3:
  285.                         i = 0;
  286.             j = get_random(maze_size_y);
  287.                         break;
  288.         }
  289.         maze[i][j] |= END_SQUARE;
  290.         maze[i][j] |= ( DOOR_OUT_TOP >> wall );
  291.     maze[i][j] &= ~( WALL_TOP >> wall );
  292.     end_x = i;
  293.     end_y = j;
  294.     end_dir = wall;
  295.  
  296.     /* set logo */
  297.     if ( (maze_size_x > 15) && (maze_size_y > 15) ) {
  298.         logo_x = get_random(maze_size_x - LOGOSIZE - 6) + 3;
  299.         logo_y = get_random(maze_size_y - LOGOSIZE - 6) + 3;
  300.  
  301.         for (i=0; i<LOGOSIZE; i++) {
  302.             for (j=0; j<LOGOSIZE; j++) {
  303.                 maze[logo_x + i][logo_y + j] |= DOOR_IN_TOP;
  304.             }
  305.         }
  306.     }
  307.     else
  308.         logo_y = logo_x = -1;
  309. }
  310.  
  311.  
  312. create_maze() /* create a maze layout given the intiialized maze */
  313. {
  314.     register int i, newdoor;
  315.  
  316.     lockcount = LOCK_COUNT_1;
  317.     pw_lock(gfx->gfx_pixwin, &pwrect);
  318.  
  319.     do {
  320.         move_list[sqnum].x = cur_sq_x;
  321.         move_list[sqnum].y = cur_sq_y;
  322.         move_list[sqnum].dir = newdoor;
  323.         while ( ( newdoor = choose_door() ) == -1 ) { /* pick a door */
  324.             if ( backup() == -1 ) { /* no more doors ... backup */
  325.                 maze_unlock(gfx->gfx_pixwin);
  326.                 return; /* done ... return */
  327.             }
  328.         }
  329.         if (global_restart)
  330.             return;
  331.  
  332.         /* mark the out door */
  333.         maze[cur_sq_x][cur_sq_y] |= ( DOOR_OUT_TOP >> newdoor );
  334.         
  335.         switch (newdoor) {
  336.             case 0: cur_sq_y--;
  337.                 break;
  338.             case 1: cur_sq_x++;
  339.                 break;
  340.             case 2: cur_sq_y++;
  341.                 break;
  342.             case 3: cur_sq_x--;
  343.                 break;
  344.         }
  345.         sqnum++;
  346.  
  347.         /* mark the in door */
  348.         maze[cur_sq_x][cur_sq_y] |= ( DOOR_IN_TOP >> ((newdoor+2)%4) );
  349.  
  350.         /* if end square set path length and save path */
  351.         if ( maze[cur_sq_x][cur_sq_y] & END_SQUARE ) {
  352.             path_length = sqnum;
  353.             for ( i=0; i<path_length; i++) {
  354.                 save_path[i].x = move_list[i].x;
  355.                 save_path[i].y = move_list[i].y;
  356.                 save_path[i].dir = move_list[i].dir;
  357.             }
  358.         }
  359.  
  360.     } while (1);
  361.  
  362. } /* end of create_maze() */
  363.  
  364.  
  365. choose_door() /* pick a new path */
  366. {
  367.     int candidates[3];
  368.     register int num_candidates;
  369.  
  370.     num_candidates = 0;
  371.  
  372. topwall:
  373.     /* top wall */
  374.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_TOP )
  375.         goto rightwall;
  376.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_TOP )
  377.         goto rightwall;
  378.     if ( maze[cur_sq_x][cur_sq_y] & WALL_TOP )
  379.         goto rightwall;
  380.     if ( maze[cur_sq_x][cur_sq_y - 1] & DOOR_IN_ANY ) {
  381.         maze[cur_sq_x][cur_sq_y] |= WALL_TOP;
  382.         maze[cur_sq_x][cur_sq_y - 1] |= WALL_BOTTOM;
  383.         draw_wall(cur_sq_x, cur_sq_y, 0);
  384.         goto rightwall;
  385.     }
  386.     candidates[num_candidates++] = 0;
  387.  
  388. rightwall:
  389.     /* right wall */
  390.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_RIGHT )
  391.         goto bottomwall;
  392.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_RIGHT )
  393.         goto bottomwall;
  394.     if ( maze[cur_sq_x][cur_sq_y] & WALL_RIGHT )
  395.         goto bottomwall;
  396.     if ( maze[cur_sq_x + 1][cur_sq_y] & DOOR_IN_ANY ) {
  397.         maze[cur_sq_x][cur_sq_y] |= WALL_RIGHT;
  398.         maze[cur_sq_x + 1][cur_sq_y] |= WALL_LEFT;
  399.         draw_wall(cur_sq_x, cur_sq_y, 1);
  400.         goto bottomwall;
  401.     }
  402.     candidates[num_candidates++] = 1;
  403.  
  404. bottomwall:
  405.     /* bottom wall */
  406.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_BOTTOM )
  407.         goto leftwall;
  408.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_BOTTOM )
  409.         goto leftwall;
  410.     if ( maze[cur_sq_x][cur_sq_y] & WALL_BOTTOM )
  411.         goto leftwall;
  412.     if ( maze[cur_sq_x][cur_sq_y + 1] & DOOR_IN_ANY ) {
  413.         maze[cur_sq_x][cur_sq_y] |= WALL_BOTTOM;
  414.         maze[cur_sq_x][cur_sq_y + 1] |= WALL_TOP;
  415.         draw_wall(cur_sq_x, cur_sq_y, 2);
  416.         goto leftwall;
  417.     }
  418.     candidates[num_candidates++] = 2;
  419.  
  420. leftwall:
  421.     /* left wall */
  422.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_IN_LEFT )
  423.         goto donewall;
  424.     if ( maze[cur_sq_x][cur_sq_y] & DOOR_OUT_LEFT )
  425.         goto donewall;
  426.     if ( maze[cur_sq_x][cur_sq_y] & WALL_LEFT )
  427.         goto donewall;
  428.     if ( maze[cur_sq_x - 1][cur_sq_y] & DOOR_IN_ANY ) {
  429.         maze[cur_sq_x][cur_sq_y] |= WALL_LEFT;
  430.         maze[cur_sq_x - 1][cur_sq_y] |= WALL_RIGHT;
  431.         draw_wall(cur_sq_x, cur_sq_y, 3);
  432.         goto donewall;
  433.     }
  434.     candidates[num_candidates++] = 3;
  435.  
  436. donewall:
  437.     if ( --lockcount == 0) {
  438.         lockcount = LOCK_COUNT_1;
  439.         maze_unlock(gfx->gfx_pixwin);
  440.         if (global_restart)
  441.             return;
  442.         pw_lock(gfx->gfx_pixwin, &pwrect);
  443.     }
  444.     if (num_candidates == 0)
  445.         return ( -1 );
  446.     if (num_candidates == 1)
  447.         return ( candidates[0] );
  448.     return ( candidates[ get_random(num_candidates) ] );
  449.  
  450. } /* end of choose_door() */
  451.  
  452.  
  453. backup() /* back up a move */
  454. {
  455.     sqnum--;
  456.     cur_sq_x = move_list[sqnum].x;
  457.     cur_sq_y = move_list[sqnum].y;
  458.     return ( sqnum );
  459. } /* end of backup() */
  460.  
  461.  
  462. draw_maze_border() /* draw the maze outline */
  463. {
  464.     register int i, j;
  465.  
  466.  
  467.     pw_lock(gfx->gfx_pixwin, &pwrect);
  468.     for ( i=0; i<maze_size_x; i++) {
  469.         if ( maze[i][0] & WALL_TOP ) {
  470.             pw_vector(gfx->gfx_pixwin,
  471.                 border_x + SQ_SIZE_X * i,
  472.                 border_y,
  473.                 border_x + SQ_SIZE_X * (i+1),
  474.                 border_y,
  475.                 PIX_SRC, 1);
  476.         }
  477.         if ((maze[i][maze_size_y - 1] & WALL_BOTTOM)) {
  478.             pw_vector(gfx->gfx_pixwin,
  479.                 border_x + SQ_SIZE_X * i,
  480.                 border_y + SQ_SIZE_Y * (maze_size_y),
  481.                 border_x + SQ_SIZE_X * (i+1),
  482.                 border_y + SQ_SIZE_Y * (maze_size_y),
  483.                 PIX_SRC, 1);
  484.         }
  485.     }
  486.     for ( j=0; j<maze_size_y; j++) {
  487.         if ( maze[maze_size_x - 1][j] & WALL_RIGHT ) {
  488.             pw_vector(gfx->gfx_pixwin,
  489.                 border_x + SQ_SIZE_X * maze_size_x,
  490.                 border_y + SQ_SIZE_Y * j,
  491.                 border_x + SQ_SIZE_X * maze_size_x,
  492.                 border_y + SQ_SIZE_Y * (j+1),
  493.                 PIX_SRC, 1);
  494.         }
  495.         if ( maze[0][j] & WALL_LEFT ) {
  496.             pw_vector(gfx->gfx_pixwin,
  497.                 border_x,
  498.                 border_y + SQ_SIZE_Y * j,
  499.                 border_x,
  500.                 border_y + SQ_SIZE_Y * (j+1),
  501.                 PIX_SRC, 1);
  502.         }
  503.     }
  504.  
  505.     if (logo_x != -1) {
  506.         if (colorwindows)
  507.         pw_rop(gfx->gfx_pixwin, border_x + 3 + SQ_SIZE_X * logo_x, 
  508.             border_y + 3 + SQ_SIZE_Y * logo_y, 
  509.             64, 64, PIX_SRC | PIX_COLOR(3), &icon_mpr, 0, 0);
  510.         else
  511.         pw_rop(gfx->gfx_pixwin, border_x + 3 + SQ_SIZE_X * logo_x, 
  512.             border_y + 3 + SQ_SIZE_Y * logo_y, 
  513.             64, 64, PIX_SRC, &icon_mpr, 0, 0);
  514.     }
  515.  
  516.     maze_unlock( gfx->gfx_pixwin );
  517.     if (global_restart)
  518.         return;
  519.     if (gfx->gfx_flags & GFX_DAMAGED)
  520.         gfxsw_handlesigwinch(gfx);
  521.     draw_solid_square( start_x, start_y, start_dir, 1);
  522.     draw_solid_square( end_x, end_y, end_dir, 1);
  523. } /* end of draw_maze() */
  524.  
  525.  
  526. draw_wall(i, j, dir) /* draw a single wall */
  527.     int i, j, dir;
  528. {
  529.     switch (dir) {
  530.         case 0:
  531.             pw_vector(gfx->gfx_pixwin,
  532.                 border_x + SQ_SIZE_X * i, 
  533.                 border_y + SQ_SIZE_Y * j,
  534.                 border_x + SQ_SIZE_X * (i+1), 
  535.                 border_y + SQ_SIZE_Y * j,
  536.                 PIX_SRC, 1);
  537.             break;
  538.         case 1:
  539.             pw_vector(gfx->gfx_pixwin,
  540.                 border_x + SQ_SIZE_X * (i+1), 
  541.                 border_y + SQ_SIZE_Y * j,
  542.                 border_x + SQ_SIZE_X * (i+1), 
  543.                 border_y + SQ_SIZE_Y * (j+1),
  544.                 PIX_SRC, 1);
  545.             break;
  546.         case 2:
  547.             pw_vector(gfx->gfx_pixwin,
  548.                 border_x + SQ_SIZE_X * i, 
  549.                 border_y + SQ_SIZE_Y * (j+1),
  550.                 border_x + SQ_SIZE_X * (i+1), 
  551.                 border_y + SQ_SIZE_Y * (j+1),
  552.                 PIX_SRC, 1);
  553.             break;
  554.         case 3:
  555.             pw_vector(gfx->gfx_pixwin,
  556.                 border_x + SQ_SIZE_X * i, 
  557.                 border_y + SQ_SIZE_Y * j,
  558.                 border_x + SQ_SIZE_X * i, 
  559.                 border_y + SQ_SIZE_Y * (j+1),
  560.                 PIX_SRC, 1);
  561.             break;
  562.     }
  563. } /* end of draw_wall */
  564.  
  565.  
  566. draw_solid_square(i, j, dir, color) /* draw a solid square in a square */
  567.     register int i, j, dir, color;
  568. {
  569.     int op;
  570.  
  571.     if (colorwindows || co